﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Fifteen_Queen
{
    class Program
    {
        static void Main(string[] args)
        {

            Console.WriteLine("请输入皇后位数：");
            string snum = Console.ReadLine();
            uint num = UInt32.Parse(snum);
            grid.size = num;

            CaluMgr temp = new CaluMgr();
            temp.start();

            Console.ReadKey();
        }
    }
}

class CaluMgr
{
    private grid currG;
    private bool isover = false;
    private int SCount = 0;
    private long lastTime;
    public CaluMgr()
    {
        currG = new grid();
    }

    public int caluCount = 0;
    public void start() {
        lastTime = (DateTime.Now.ToUniversalTime().Ticks - 621355968000000000) / 10000000;

        while (!isover) {
            findingAnswer();
            caluCount++;
            //Console.WriteLine(caluCount);
        }
    }

    public void findingAnswer()
    {
        bool isS = currG.tryToNext();

        if (isS)
        {
            inDeep();
        }
        else
        {
            backdate();
        }
    }

    public void inDeep()
    {
        if (currG.deep >= grid.size - 1)
        {
            //到底层了
            //记录结果
            SCount++;
            //回溯
            backdate();
            return;
        }

        if (currG.next == null) currG.genGrid();

        currG = currG.next;

    }

    public void backdate()
    {
        grid last = currG.last;
        if (last == null)
        {
            long currT = (DateTime.Now.ToUniversalTime().Ticks - 621355968000000000) / 10000000;
            //找完了所有的解
            Console.WriteLine("找完了所有的解  结果为：" + SCount  + "  总计算次数:" + caluCount  + "用时秒:" + (currT - lastTime));
            Console.ReadKey();
            isover = true;
            return;
        }
        currG.hpos = -1;
        currG = last;
    }
}


//格子
class grid
{
    protected int _deep = 0;
    public static uint size = 4;
    public int hpos = -1;
    public grid last;
    public grid next;
    private uint[,] mask;
    private uint[,] _globalMask;
    private bool _isFinish = false;  //找完了？
    public bool isFinish { get { return _isFinish; } }
    public int deep { get { return _deep; } }
    public grid()
    {
        mask = new uint[size, size];
        _globalMask = new uint[size, size];
    }

    public bool tryToNext()
    {
        bool isFind = false;
        if (hpos >= size - 1)
        {
            _isFinish = true;
            return isFind;
        }

        if (last != null)
        {
            uint[,] tmask = last.globalMask;//用父类的 mask
            for (int i = hpos + 1; i < size; i++)
            {
                if (tmask[_deep, i] <= 0)
                {
                    hpos = i;
                    isFind = true;
                    break;
                }
            }
        }
        else
        {
            hpos++;
            isFind = true;
        }


        if (!isFind)
        {
            _isFinish = true;
            return isFind;
        }
        CalcMask();
        return isFind;
    }

    public void genGrid()
    {
        grid sub = new grid();
        sub.last = this;
        next = sub;
        sub._deep = _deep + 1;
    }

    private bool isChange = false;
    public void CalcMask()
    {
        // 横、竖、斜
        int x = hpos;
        int y = _deep;

        for (int i = 0; i < size; i++)
        {
            for (int j = 0; j < size; j++)
            {
                mask[i, j] = 0; //清零
                if (x == j || y == i)
                {  //横、竖标记
                    mask[i, j] = 1;
                    continue;
                }
                if (x - j == y - i)
                {  //右斜 标记
                    mask[i, j] = 1;
                    continue;
                }
                if ((x - j) + (y - i)  == 0)
                {  //左斜 标记
                    mask[i, j] = 1;
                    continue;
                }
            }
        }

        isChange = true;
    }

    public uint[,] globalMask
    {
        get
        {
            if (isChange) {
                for (int i = 0; i < size; i++)
                {
                    for (int j = 0; j < size; j++)
                    {
                        _globalMask[i, j] = 0;
                        _globalMask[i, j] = mask[i, j];
                        if (last != null)
                        {
                            _globalMask[i, j] += last.globalMask[i, j];
                        }
                    }
                }
                isChange = false;
            }
            return _globalMask;
        }
    }

}



